Digital data is transmitted in a wide variety of different contexts ranging from data transfers between nodes in a network to data transfers between a host and a memory in a computer system. With transmission rates increasing and voltage levels decreasing, the likelihood of an error occurring when data is transmitted can be significant. Detecting transmission errors is critical. One technique for detecting transmission errors is the cyclic redundancy check (“CRC”).
The mathematics on which CRC techniques are based is the Galois or Finite Field theory. According to theory, all operations performed in a finite field result in an element within that field. The CRC technique is based on a field containing only two elements, i.e., GF(2): {0, 1}. Arithmetic is modulo(2). In modulo(2), addition and subtraction operations are equivalent to a bitwise XOR operation. Multiplication is equivalent to a bitwise AND operation. Long division, which requires one or more subtractions, may be performed using bitwise XOR operations. In CRC techniques, bits of data are represented by polynomials, which are a function of a dummy variable “x” and have coefficients that are either 0 or 1. For example, the bits 1011 may be represented by 1·x3+0·x2+1·x+1.
When a CRC technique is used, the message or information bits are transmitted along with a CRC code. The CRC code (also referred to as a “CRC” or “checksum”) is typically appended to the end of the message. The CRC code is determined by dividing the message polynomial by a generator polynomial using polynomial division in GF(2). The remainder is the CRC. In general, the message polynomial may be any length, but the CRC is always a fixed length equal to the length of the generator polynomial. A variety of generator polynomials are available. Historically, a shift register configured with feedback according to the generator polynomial has been used to calculate CRC codes. The message is input serially to the linear feedback shift register (LFSR), one bit per clock. After the entire message has been input, the value stored in the LFSR is the remainder or CRC code.
A receiver determines whether the message has been received without error by dividing the generator polynomial into the message polynomial (and appended CRC). Generally, if the remainder is zero, there is a high likelihood that the message has been received without transmission error. The CRC code may be stripped from the received message and the data processed or stored. On the other hand, if the remainder is not equal to zero, the received message includes a transmission error and appropriate action may be initiated, e.g., request re-transmission.
To compute a CRC code for a message to be transmitted or to check a received message for a transmission error using an LFSR, one clock cycle for each bit of the message is required. Because an LFSR processes information bits serially, this approach is generally too slow to handle the high data transmission speeds used in many networks and busses.
It is known to compute CRCs using a network of exclusive OR gates instead of a LFSR. When an XOR network is used, two or more bits of a message are input in parallel to the network. FIG. 1 illustrates an example in which 16 bits (d00-d15) are input in parallel. Typically, the number of bits input in parallel is equal to the degree of the generator polynomial. The process is iterative. Groups of bits are repeatedly input to the XOR network to produce intermediate results until the entire message has been input. Intermediate results are repeatedly fed back to be added to the next group of bits. As the number of bits that are input in parallel increases, however, the XOR network increases in complexity and depth, which in turn increases the time required for a signal to propagate through the network. In addition, each new group of bits must be XORed with a previous intermediate result before being input to the XOR network, further increasing the time required to compute intermediate results. While known approaches for parallel computation of CRC codes are able to handle the transmission speeds used in some networks and busses, transmission speeds are increasing further and the known approaches are too slow to handle the high data transmission speeds in many modern networks and busses. Accordingly, there is a need for speed-optimized circuits and methods for computation of cyclic redundancy check codes.